1. Field of the Invention
This invention relates generally to circuits, and, more particularly, to dynamic constant folding of circuits.
2. Description of the Related Art
Digital circuitry in modern computing devices is generally used to produce one or more output signals in response to one or more input signals. To take a very simple example, an AND gate receives two inputs that may correspond to a binary 1 or a binary 0. The output of the AND gate is a binary 1 if the two inputs are both either 1s or 0s and a binary 0 if the two inputs are different. More complicated circuits, such as processors, memory elements, application-specific integrated circuits, and the like may be formed by combining simple logical elements such as AND gates. The values of the inputs and/or outputs of digital circuits are typically evaluated in time with a clock. For example, the values of the outputs of a digital circuit may be determined based on the values of the inputs on a rising edge of a clock signal. Accordingly, the state of the digital circuit may change, or be allowed to change, at the clock frequency.
Although the overall state of the digital circuit typically varies with the clock frequency, some inputs to portions of the digital circuit may change at a frequency that is less than the clock frequency used to drive the digital circuit. In some cases, inputs to a portion of the digital circuit may remain unchanged largely by coincidence. However, in other cases, one or more inputs to a portion of the digital circuit may remain predictably constant over a time period that is larger than the clock period. Accordingly, the digital circuit may be simplified by assuming that the input is equal to the constant value for the number of clock cycles over which the input remains constant. When the input changes to a different constant value, the digital circuit may be correspondingly modified. Accordingly, the digital circuit may vary with a frequency equal to the frequency of variation of the input. Simplifying a digital circuit by assuming constant values of one or more inputs for a selected period of time is conventionally referred to as “constant folding.”
FIG. 1 conceptually illustrates a conventional static implementation of a circuit 100 and a constant-folded circuit 105 corresponding to the circuit 100. The circuit 100 receives inputs A and B and produces a corresponding output C. Input A is assumed to vary at the clock frequency and input B varies at a frequency that is less than the clock frequency. Accordingly, the circuit 100 remains static and the output C of the circuit 100 varies at the clock frequency. The constant-folded circuit 105 receives input A, performs the same operations on the input A as are performed by the circuit 100 for a selected constant value of the input B, and produces a corresponding output C. However, since the input B varies at a frequency that is less than the clock frequency, the output C of the constant-folded circuit 105 also varies at the frequency of the input B.
The structure of the constant-folded circuit 105 is typically determined by information included in an active configuration memory. The contents of the active configuration memory may be varied to change the structure of the constant-folded circuit 105 to correspond to different values of the constant inputs B. For example, the constant-folded circuit 105 may be implemented as a Field Programmable Gate Array (FPGA) and the inputs to the FPGA lookup table may be stored in the active configuration memory. The structure of the constant-folded circuit 105 may be varied at the frequency of the input B by providing new information to the active configuration memory at the frequency associated with the input B. For example, different programming inputs responding to different values of the input B may be generated at design-time (i.e., statically) and stored by the system. The stored programming inputs may then be provided to the active configuration memory at the frequency associated with the input B. However, static generation and storage of constant folded system configurations limits the applicability of reconfiguration. For example, the cost of storage can be prohibitive if the number of different constant values is large. In addition, if configurations are stored off-chip, the I/O bandwidth required to load them on demand may be prohibitively large.
Reconfiguring the constant-folded circuit 105 during operation may result in spurious outputs, which may be propagated to the rest of the system. Consequently, conventional constant-folding requires that the constant-folded circuit 105 halt computation during the reconfiguration process in order to isolate the unknown transitory state of the constant-folded circuit 105 from target areas that may receive the spurious results produced during the reconfiguration. For example, computation may be halted by pruning the system clock, setting the target areas equal to constants for the duration of the reconfiguration process, or setting a reconfiguration flag.
Halting computation results in downtime for the computational fabric that includes the constant-folded circuitry, regardless of the particular technique used to halt computation. The downtime may be amortized over computation time by restricting reconfiguration to inputs that change relatively infrequently when compared to the system clock frequency. However, restricting constant folding to variables that change relatively infrequently limits the number of instances in which constant folding may be applied. Alternatively, the computational fabric downtime may be reduced by providing chip-level architectural features that enable rapid reconfiguration speeds. However, the chip level architectural features consume valuable die area and may result in a reduction in performance of circuits on the chip, which may reduce the number of applications of the computational fabric.